package com.laotang.第_15_章_图论算法.力扣_210_课程表二;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

public class _210_course_schedule_ii {

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] res = new int[numCourses];
        // 1. 建图，邻接表
        Set<Integer>[] g = new HashSet[numCourses];
        for (int i = 0; i < numCourses; i++) {
            g[i] = new HashSet<Integer>();
        }

        // 计算每个节点的入度
        int[] indegrees = new int[numCourses];
        for (int[] prerequisite : prerequisites) {
            int w = prerequisite[0];
            int v = prerequisite[1];
            // 方向 v -> w
            g[v].add(w);
            indegrees[w]++;
        }

        // 2. BFS 遍历
        Queue<Integer> queue = new LinkedList<Integer>();
        // 先将入度为 0 的节点放到队列中
        for (int v = 0; v < numCourses; v++) {
            if (indegrees[v] == 0) queue.add(v);
        }

        int index = 0;
        while (!queue.isEmpty()) {
            int v = queue.remove();
            res[index++] = v;
            for (int w : g[v]) {
                indegrees[w]--;
                if (indegrees[w] == 0) queue.add(w);
            }
        }
        // 判断是否存在环
        if (index != numCourses) return new int[0];
        return res;
    }
}
